package com.singzi.algorithm;

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {

        int[]arr = {2,3,4,5,56,-100,76,78,8,7,45,6,-1};
        Heap heap = new Heap();
        heap.heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

}
class Heap{
    public void heapSort(int[]arr){
        int n = arr.length;

        buildMaxHeap(arr, n);
        for(int i = n-1;i >= 0;i--){
            swap(arr, 0, i);
            n--;
            headJust(arr, 0, n);
        }
    }
    private void buildMaxHeap(int[]arr, int n) {
        for(int i = n/2;i >= 0;i--){
            headJust(arr, i, n);
        }
    }
    private void headJust(int[] arr, int index, int n) {

        int temp = arr[index];
//        System.out.println("__________________________");
        for(int i = 2*index+1;i < n;i = 2*i+1){
            if(i+1 < n && arr[i] < arr[i+1]){ //如果左子树小于右子树
                i++;                          //比较根节点和右子树
            }
            if(arr[i] > temp){                //如果子树大于根节点，交换子树和根节点
                swap(arr, index, i);
                index = i;                    //交换后，子树可能收到影响，继续对子树进行处理
            }else {
                break;                        //根节点大于子树，不用处理
            }
        }
    }

    private void swap(int[] arr, int index, int i) {
        int temp = arr[index];
        arr[index] = arr[i];
        arr[i] = temp;
    }
}
